package leetcode.匹配;

/**
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 *
 * @author https://leetcode-cn.com/problems/regular-expression-matching/
 * <p>
 * <p>
 * 和 44 题相似 以及剑指offer第19题
 */
public class Test10正则表达式匹配 {
    public boolean isMatch(String s, String p) {
        char[] str = s.toCharArray();
        char[] pattern = p.toCharArray();
        return match(str, pattern);
    }

    public static boolean match(char[] str, char[] pattern) {
        return matchStr(str, 0, pattern, 0);
    }


    public static boolean matchStr(char[] str, int i, char[] pattern, int j) {

        if (i == str.length && j == pattern.length) {
            // 字符串和模式串都为空
            return true;
        }

        if (j == pattern.length) {
            // 模式串为空
            return false;
        }

        // 模式串下一个字符是'*'
        boolean next = (j + 1 < pattern.length && pattern[j + 1] == '*');
        /*
            aaa

            a.a

            ab*ac*a

            a.*ac*a

         */
        if (next) {
            // 模式串与当前的 str指向的数值一样，就让他们各自前进，j 前进 2 位跳过 * 号
            if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
                // 注意这里存在两种情况，一种是字符串不动，模式串移动两个以跳过 * 号（因为*可以代0个字符）
                // 另一种是字符串移动一个，但是模式串不动（因为 * 可以代表多个它前面的字符，但是具体是多少个
                // 我们不知道，只能让字符串移动，但是只要能进入这个判断条件里面，就代表着匹配成功
                // 最后字符串会走到匹配失败，但是模式串留在原地，此时进入else语句）
                // else 语句里面就是属于只让模式串移动两个位置的算法，此时模式串会快速匹配上文中字符串移动的个数（这也就代表着*究竟代表着几个字符）
                return matchStr(str, i, pattern, j + 2) || matchStr(str, i + 1, pattern, j);
            } else {
                // 模式串需要忽略 * 前面的所有数值
                return matchStr(str, i, pattern, j + 2);
            }
        } else {
            if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
                // 最理想的情况就是模式串和字符串都是一样的，不同的都是 .
                return matchStr(str, i + 1, pattern, j + 1);
            } else {
                return false;
            }
        }
    }
}
